class Solution {
    //自上而下进行动态规划时，我们发现子问题之间存在重复的更小问题
    //为避免不必要的重复运算，我们可以考虑用自下而上的循环来实现
    //先求出子问题的最优解，再基于子问题的解计算更大的问题
    //时间复杂度O(n):计算f(n)需循环n次，每次循环操作复杂度为O(1)
    //空间复杂度O(1)
public:
    int fib(int n) {
        if(n < 0) return 0;
        else if((0 == n) || (1 == n)) return n;
        else{
            //n >= 2
            int nSub1 = 1; //fib(1)开始,代表fib(n-1)
            int nSub2 = 0; //fib(0)开始,代表fib(n-2)
            int fibPlus = 0;  //fib(n-1) + fib(n-2)
            for(int i = 2; i <= n; ++i){
                fibPlus = (nSub1 + nSub2) % 1000000007;  //需要求模
                nSub2 = nSub1 % 1000000007;
                nSub1 = fibPlus;
            }
            return fibPlus;
        }
    }
};